#Some useful sage functions to factorize RSA by GCD(). 
#The source is awfull! only a PoC
#provide 1024mods.txt from certparser with:
#sqlite3 ./certparser.db "SELECT modulus FROM x509 WHERE size=1024" > 1024mods.txt

primes = []
fmods = {}
uniq_prime = []

log = open('./debug.log', 'w')

def iterhgcd(base, modtable):
    counter = 0
    for modulo in modtable:
        result = hgcd(base, modulo)
        if result != 1:
            if result == h2d(modulo):
                print "collision: %d" % result
            else:
                print counter, result
        else:
            counter += 1

def hgcd(a, b):
    return gcd(h2d(a), h2d(b))

def iterhgcd(base, modtable):
    counter = 0
    for modulo in modtable:
        if modulo == base:
            #print "collision!"
            counter += 1
            continue
        else:
            result = hgcd(base, modulo)
            if result != 1:
                print counter, result, base, modulo
                p = result
                q = h2d(modulo)/result
                m = h2d(modulo)
                primes.append([p, q, m])
                fmods[modulo] = [p, q]
                log.write('%s;%d;%d;\n') % (modulo,p,q)
            counter += 1    

def h2d(hexstring):
    try:
        int(hexstring[:-1], 16)
    except ValueError:
        print hexstring
    return int(hexstring[:-1], 16)

modfile = open('1024mods.txt', 'r')
modtable = modfile.readlines()

def iterate_all(modules):
    for base in modules:
        iterhgcd(base, modules)
    modules.remove(base)
        
def make_uniq_primes():
    for primerow in primes:
        if not uniq_prime.count(primerow[0]):
            uniq_prime.append(primerow[0])
        if not uniq_prime.count(primerow[1]):
            uniq_prime.append(primerow[1])    
            
#time iterate_all(modtable) # <- this does the magic.


